package demo.practice.leetcode_offer;

import java.util.HashMap;
import java.util.Map;

public class Offer10_1 {


    Map<Integer, Integer> map = new HashMap<>();

    //1备忘录
    public int fib(int n) {

        if (map.containsKey(n))
            return map.get(n);
        if (n < 0)
            return -1;
        if (n == 0 || n == 1)
            return n;
        int res = fib(n - 1) + fib(n - 2);

        res %= 1000000007;
        map.put(n, res);
        return res;
    }


}
